//https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=23457&ru=%2Fpractice%2F459bd355da1549fa8a49e350bf3df484&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思路：1.先定义一个规则，当前两个堆的总数和是偶数，那么就加入大顶堆；两个堆的总数和是奇数，那么就加入小顶堆；
//     2.当push 大顶堆时，如果当前小顶堆的最小值<待加入数，那么先过一遍小顶堆，弹出top，再加入大顶堆；
//     3.当push 小顶堆时，如果当前大顶堆的最大值>待加入数，那么先过一遍大顶堆，弹出top，再加入小顶堆；
//     4.下面这个解法，就是不管大不大，小不小，都过一遍，属于比较暴力了；

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 数据流中的中位数
class Solution {
public:
    void Insert(int num){
         /*
         * 当两堆的数据个数相等时候，左边堆添加元素。
         * 采用的方法不是直接将数据插入左边堆，而是将数据先插入右边堆，算法调整后
         * 将堆顶的数据插入到左边堆，这样保证左边堆插入的元素始终是右边堆的最小值。
         * 同理左边数据多，往右边堆添加数据的时候，先将数据放入左边堆，选出最大值放到右边堆中。
         */
        if (maxHeap.size() == minHeap.size()) {
            minHeap.push(num);
            int top = minHeap.top();
            minHeap.pop();
            maxHeap.push(top);
        } else {
            maxHeap.push(num);
            int top = maxHeap.top();
            maxHeap.pop();
            minHeap.push(top);
        }
    }

    double GetMedian(){
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top()+minHeap.top())*1.0/2;
        } else {
            return maxHeap.top()*1.0;
        }
    }
    // 最大堆，存储左边一半的数据，堆顶为最大值
    priority_queue<int, vector<int>, less<int>> maxHeap;
    // 最小堆， 存储右边一半的数据，堆顶为最小值
    priority_queue<int, vector<int>, greater<int>> minHeap;
};

